The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.
One mechanism for controlling access to resources uses locks. A lock on a resource is a data structure which indicates that a particular entity has been granted certain rights with respect to the resource. There are many types of locks. Locks of certain types may be shared by many entities, while locks of other types prevent any other locks from being granted on the same resource.
In one example, a table and the records stored therein may be a resource that is accessed by entities, such as, for example, processes executing in one or more computer systems. In this example, ownership of a NULL lock on the table grants a process no permission to access the table in any manner. Ownership of an exclusive lock grants a process permission to do anything with a table, and guarantees that no other process is performing any operation on the table. Due to the various permissions and guarantees associated with the above types of locks, certain lock combinations are not allowed. For example, if a process owns an exclusive lock on a resource, then no other process can be granted any lock other than a NULL lock.
A type of lock that may be held by more than one entity at a time is referred to herein to as a share lock. For example, two processes can concurrently hold read locks on the same resource at the same time, so read locks are one type of share locks. For the purposes of explanation, the following description shall refer to exclusive locks, share locks, and NULL locks.
Before an entity can perform an operation on a resource, the entity is required to obtain a lock that grants the entity the right to perform the desired operation on the resource. To obtain a lock, an entity transmits a request for the lock to a lock manager. A lock manager is a process executing in a computer system that is responsible for granting, queuing, and keeping track of locks on one or more resources. To manage the use of resources in a distributed system, lock managers may be executed on one or more nodes in the distributed system.
According to one past approach for managing locks, a lock manager implements two types of objects: a resource object and a lock. Resource objects are data structures that correspond to actual resources. The lock manager establishes a mapping between actual resources and resource objects. Each resource object is associated with two queues: a granted queue and a convert queue. The granted queue is an unordered list of locks that have been granted. The convert queue is a partially ordered list of locks that have been requested, but not yet granted. Typically, a request for a lock is actually a convert request, where a process holding a lock is requesting that the lock it holds be converted from one type of lock to a different type of lock. The lock manager attaches locks to the grant queues of resource objects to indicate that the entity identified in the lock has been granted a lock of the type indicated in the lock on the resource that corresponds to the resource object to which the lock is attached.
FIG. 1 is a block diagram illustrating a lock manager 106 that is implemented according to this past approach. Lock manager 106 is a process that is configured to manage the locks on resource objects, such as resource object 100, that are stored in a memory 108. Resource object 100 is associated with a granted queue 102 and a convert queue 104. Lock manager 106 has attached three locks 110, 112 and 114 to the granted queue 102, and one convert request 130 to the convert queue 104.
All locks and convert requests have an entity ID portion and a lock type portion. The entities identified by the entity IDs may be any entities that are capable of requesting locks, such as, for example, processes executing in a computer system. In FIG. 1, the entity ID portion 116 of lock 110 indicates that an entity ENTITY_1 owns lock 110, and the lock type portion 118 of lock 110 indicates that lock 110 is an exclusive lock. The entity ID portion 120 of lock 112 indicates that lock 112 is owned by an entity ENTITY_2, and the lock type portion 122 of lock 112 indicates that lock 112 is a NULL lock. The entity ID portion 124 of lock 114 indicates that lock 114 is owned by an entity ENTITY_3, and the lock type portion 126 of lock 114 indicates that lock 114 is a NULL lock. The entity ID portion 132 of convert request 130 indicates that convert request 130 is associated with entity ENTITY_4, and the lock type portion 136 of convert request 130 indicates that ENTITY_4 currently holds a NULL lock on the resource. In addition to a lock type portion 136, convert request 130 also includes a requested lock type portion 134 which indicates that ENTITY_4 is requesting an exclusive lock.
Lock manager 106 has attached locks 110, 112 and 114 to granted queue 102, indicating that ENTITY_1 currently has exclusive ownership of the resource that corresponds to resource object 100. Lock manager 106 has attached convert request 130 to the convert queue 104, indicating that ENTITY_4 has requested but has not yet been granted an exclusive lock on the resource associated with resource object 100.
According to the lock manager implementation illustrated in FIG. 1, information pertaining to any given resource may be stored in the resource object that corresponds to the resource. Further, when the lock manager of FIG. 1 is used to manage a plurality of resources in a distributed system, each resource object associated with a resource is stored in the memory of a single node of the distributed system.
According to the above lock management approach, an entity may initially establish a NULL lock on all resources that the entity will possibly use. Then, when the entity actually requires access to a resource, the entity requests that its NULL lock be converted to a lock that grants to the entity the rights to perform the desired operation. However, this lock convert request may be granted only when there are no conflicting locks that are currently granted on the resource.
For example, to delete a table, a process must obtain an exclusive lock on the resource object that corresponds to the table. To obtain the exclusive lock, the process transmits a message to the lock manager that controls the resource object that corresponds to the table. In the message, the process requests that its current NULL lock be converted to an exclusive lock. If no other process currently holds an exclusive lock on the table, and if no currently granted locks (such as any share locks) would prevent the grant of an exclusive lock, then the current lock held by the requesting process is converted to an exclusive lock. However, if a share lock on the table has already been granted to some process (the “blocking” process), then an exclusive lock cannot be immediately granted. Under these circumstances, the lock convert request is placed on the convert queue of the resource object. When the blocking process is ready to release the share lock it holds on the table, the blocking process may send a lock release request to the lock manager. Alternatively, the lock manager may send a message with a down-convert request to the blocking process requesting that the share lock on the resource be released. After the lock manager receives the lock release request from the blocking process, the lock manager converts the share lock held by the blocking process to a lesser lock that allows the grant of the exclusive lock. The requested exclusive lock is then granted and a message is sent to the requesting process to inform the requesting process that the exclusive lock has been granted.
The above lock management approach, however, has some disadvantages when it is implemented in a distributed system that includes numerous entities capable of requesting resources that are shared throughout the system. One such disadvantage is an impeded read-write concurrency to resources.
For example, the distributed system may be a cluster of database server instances, where each instance executes in its own memory space and where the different instances may execute on the same or different computer systems. In this database server cluster system, each instance in the cluster of database server instances has read-write access to data blocks on a storage medium, such as, for example, shared hard disks or a Storage Area Network (SAN). The data blocks on the storage medium typically store the data of one or more databases that are managed by one or more of the database server instances of the cluster.
In such a database server cluster, it is not uncommon for many database server instances to concurrently hold share locks on the same data block. The set of database server instances that hold share locks on a particular data block are collectively referred to in this example as the “share lock holders”. The database server instance that is associated with the lock manager that manages the locks on a particular data block is referred to in this example as the “master” of the data block.
If one of the share lock holders (the “requestor”) wants to convert its share lock on a particular data block to an exclusive lock, the requestor has to first send a convert request to the master of that data block in order to upgrade its share lock to an exclusive lock. When this shared-to-exclusive convert request reaches the head of the convert queue at the master of the data block, the master sends down-convert request messages to all share lock holders asking them to down-convert or release (close) the share locks they hold on that data block. The master can grant the exclusive lock on the data block to the requestor only after all share lock holders acknowledge to the master that they have down-converted or released the share locks on the data block that they were holding.
However, between the time the requester sends the shared-to-exclusive convert request and the time that the exclusive lock on the data block is granted, the requestor, and/or any transaction executing at the requestor that involves that data block, has to wait. The requestor cannot start modifying the data block or perform any related subsequent work even though the requestor may already have a current copy of the data block in its shared memory and is certain (by virtue of its share lock on the data block) that no process or transaction executing on any other database server instance in the cluster is allowed to modify the data block on the storage medium. Further, this read-write concurrency problem is exacerbated in a database server cluster with many instances because the number of share lock holders may be quite large and because before granting the exclusive lock on the data block the master must wait for lock release or down-convert acknowledgements from all of the share lock holders.
Although the read-write concurrency disadvantage of the past lock management approach is presented above with respect to data blocks and instances in a database server cluster, it is noted that this disadvantage is not unique to lock management in database server clusters. Rather, this read-write concurrency disadvantage is common to any lock management approach for controlling access to shareable resources in a distributed system.
Based on the foregoing, there is a clear need for techniques for improved read-write concurrency that overcome the disadvantage of the past lock management approach described above.